package com.zet.algorithm;

/**
 * 选择排序算法
 *
 * 时间复杂度：
 *   选择排序的时间复杂度是O(N2)：假设被排序的数列中有N个数。
 * 遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次因此，
 * 选择排序的时间复杂度是O(N2)。
 *
 * 稳定性：
 *    选择排序是稳定的算法，它满足
 * 稳定算法的定义：假设在数列中存在a[i]=a[j]，若在排序之前，
 * a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的
 * @Author: zet
 * @Date: 2018-03-25 21:13
 */
public class SelectSort {

    /**
     * 排序
     * @param arr 待排序的数组
     * @return 有序数组
     */
    public static int[] sort(int[] arr) {
        int len = arr.length;

        int minIndex;
        for (int i = 0; i < len ; i++) {
            minIndex = i;
            for (int j = i+1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }

        }
        return arr;
    }
}
